package cn.ly.stack;

public class Reverser {
	
	private String input;
	private String output;
	public Reverser(String in){
		this.input = in;
	}
	
	public String doRev(){
		int stackSize = input.length();
		StackT<Integer> theStack = new StackT<Integer>(stackSize);
		for(int i=0; i<input.length(); i++){
			char ch = input.charAt(i);
			theStack.push(ch);
		}
		StringBuilder sb = new StringBuilder();
		while(!theStack.isEmpty()){
			sb.append((char)theStack.pop().intValue());
			sb.reverse();
		}
		return this.output = sb.toString();
	}
	
	public static void main(String[] args) {
		String str1 = reverse("Unicode字符编码范围_百度文库".toCharArray(),"Unicode字符编码范围_百度文库".length());
		System.out.println(str1);
		str1 = reverse(str1,0);
		System.out.println(str1);
		
	}
	
	//O(n)
    public static String reverse(char[] value,int count) {
        int n = count - 1;
        for (int j = (n-1) >> 1; j >= 0; --j) {//(n-1) >> 1，不用(n-1)/2，用左移
            char temp = value[j];
            char temp2 = value[n - j];
         
            value[j] = temp2;
            value[n - j] = temp;
        }
        return String.valueOf(value);
    }
    
    //更快的O(log n)的字符串逆序
    public static String reverse(String str,int i){
    	StringBuilder sb = new StringBuilder(str);
    	int len = sb.length();
    	int halfLen = len/2;
    	if(len == 1){
    		return str;
    	}
    	String upHalf = sb.substring(0, halfLen);
    	String downHalf = null;
    	if( (len & 1) == 0){
    		downHalf = sb.substring(halfLen, len);
    		return new StringBuilder(reverse(downHalf,i)).append(reverse(upHalf,0)).toString();
    	}else{
    		downHalf = sb.substring(halfLen+1, len);
    		return new StringBuilder(reverse(downHalf,i)).append(sb.substring(halfLen, halfLen+1)).append(reverse(upHalf,0)).toString();
    	}
    	
    }


}
